package codingforgreat.class36;

import java.util.*;

//Lc815
public class Class11_BusRoutes {
    public int numBusesToDestination(int[][] routes, int source, int target) {
        if(source == target){
            return 0;
        }
        HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
        for(int i = 0; i < routes.length;i++){
            for(int j = 0;j < routes[i].length;j++){
                if(!map.containsKey(routes[i][j])){
                    map.put(routes[i][j],new ArrayList<>());
                }
                map.get(routes[i][j]).add(i);
            }
        }
        if(!map.containsKey(source) || !map.containsKey(target)){
            return -1;
        }
        ArrayList<Integer> queue = new ArrayList<>();
        boolean[] set = new boolean[routes.length];
        for(int router : map.get(source)){
            queue.add(router);
            set[router] = true;
        }
        int len = 1;
        while(!queue.isEmpty()){
            ArrayList<Integer> next = new ArrayList<>();
            for(int router : queue){
                int[] bus = routes[router];
                for(int station : bus){
                    if(station == target){
                        return len;
                    }
                    for(int rou : map.get(station)){
                        if(!set[rou]){
                            set[rou] = true;
                            next.add(rou);
                        }
                    }
                }
            }
            queue = next;
            len++;
        }
        return -1;
    }
}
